//
// 分别用递归和非递归方式实现二叉树先序、中序和后序遍历
// Created by Liming Shao on 10/25/2017.
//

#include "C088.h"
#include <iostream>
#include <stack>

void C088::preOrderRecur(Node *head) {
    if(head != nullptr){
        std::cout << head->value << " ";
        preOrderRecur(head->left);
        preOrderRecur(head->right);
    }
}

void C088::inOrderRecur(Node *head) {
    if(head != nullptr){
        inOrderRecur(head->left);
        std::cout << head->value << " ";
        inOrderRecur(head->right);
    }
}

void C088::posOrderRecur(Node *head) {
    if(head != nullptr){
        posOrderRecur(head->left);
        posOrderRecur(head->right);
        std::cout << head->value << " ";
    }
}

// 有难度
void C088::preOrderUnRecur(Node *head) {
    if(head==nullptr)
        return;

    std::stack<Node*> nodeStack;
    nodeStack.push(head);
    Node* tmp = nullptr;
    while(!nodeStack.empty()){
        tmp = nodeStack.top();
        nodeStack.pop();
        std::cout << tmp->value << " ";

        if(tmp->right != nullptr)
            nodeStack.push(tmp->right);

        if(tmp->left != nullptr)
            nodeStack.push(tmp->left);
    }
}

// 有难度
void C088::inOrderUnRecur(Node *head) {
    std::stack<Node*> nodeStack;
    Node* tmp = head;
    while(!nodeStack.empty() || tmp != nullptr){
        if(tmp!=nullptr){
            nodeStack.push(tmp);
            tmp = tmp->left;
        }else{
            tmp = nodeStack.top();
            std::cout << tmp->value << " ";
            nodeStack.pop();

            tmp= tmp->right;
        }
    }
}

void C088::posOrderUnRecur(Node *head) {
    if(head == nullptr)
        return;

    std::stack<Node*> nodeStack;
    nodeStack.push(head);

    Node* last = nullptr;
    Node* current = nullptr;

    while(!nodeStack.empty()){
        current = nodeStack.top();

        if((current->left != nullptr) && (last != current->left) && (last != current->right || last == nullptr)){
            nodeStack.push(current->left);
        } else if(current->right != nullptr && last != current->right){
            nodeStack.push(current->right);
        } else{
            std::cout << current->value << " ";
            last = current;
            nodeStack.pop();
        }
    }


}

void C088::test() {
    /*
     *  使用如下二叉树
     *          1
     *        2    3
     *      4  5  6  7
     *     8        9  10
     *
     *  前序遍历：1 2 4 8 5 3 6 7 9 10
     *  中序遍历：8 4 2 5 1 6 3 9 7 10
     *  后序遍历：8 4 5 2 6 9 10 7 3 1
     */

    Node *head = newNode(1);
    head->left = newNode(2);
    head->right = newNode(3);
    head->left->left = newNode(4);
    head->left->right = newNode(5);
    head->right->left = newNode(6);
    head->right->right = newNode(7);
    head->left->left->left = newNode(8);
    head->right->right->left = newNode(9);
    head->right->right->right = newNode(10);

    std::cout << "\npreOrderRecur: ";
    preOrderRecur(head);

    std::cout << "\ninOrderRecur: ";
    inOrderRecur(head);

    std::cout << "\nposOrderRecur: ";
    posOrderRecur(head);

    std::cout << "\npreOrderUnRecur: ";
    preOrderUnRecur(head);

    std::cout << "\ninOrderUncur: ";
    inOrderUnRecur(head);

    std::cout << "\nposOrderUnRecur: ";
    posOrderUnRecur(head);
}

C088::Node *C088::newNode(int val) {
    Node *ret = (Node*)malloc(sizeof(Node));
    ret->value = val;
    ret->left = nullptr;
    ret->right = nullptr;
    return ret;
}

void C088::echoLeft(C088::Node *node) {
    preOrderRecur(node->left);
}

void C088::echoRight(C088::Node *node) {
    preOrderRecur(node->right);
}
